Matthias Jantzen
| Überblick über das Gebiet der endlichen Automaten. Selbstständiges Einarbeiten in einen Problembereich. Umgang mit wissenschaftlicher, zum großen Teil englischsprachiger Literatur. Die adäquate Präsentation eines formalen Themenkomplexes in schriftlicher und verbaler Form ist vorrangiges Lernziel dieses Proseminars. | |
| Endliche Automaten und eng mit ihnen verwandte Begriffe, wie z.B. lineare Grammatiken und rationale Ausdrücke, gehören zu den wichtigsten Grundbegriffen der Informatik. Sie dienen zur Beschreibung und Analyse von technischen Geräten, von Systemen und Prozessen unterschiedlichster Art, von Algorithmen und Programmen. Viele Konzepte der theoretischen Informatik, wie z.B. der Kellerautomat und die Turingmaschine, bauen auf der Theorie der endlichen Automaten auf. Neben den Automaten selbst (Begriffe: Moore- und Mealy-Automat, Rabin-Scott-Automat, Minimierung, Äquivalenz von Automaten, Nicht-Determinismus) werden zu ihnen äquivalente Darstellungen wie reguläre Ausdrücke und Typ-3-Grammatiken vorgestellt. Des Weiteren sind Vorträge zu Anwendungsbeispielen, wie lexikalischer Analyse und Patternmatching, geplant. | |
| Grundstudium | |
| keine | |
| Referate der TeilnehmerInnen und Ausarbeitung von Zusammenfassungen. | |
| W. Brauer: Automatentheorie J. Hopcroft & J. Ullmann: Introduction to Automata Theory, Languages and Computation T.A. Sudkamp: Languages and Machines A. Salomaa: Jewels of Formal Language Theory und weitere, in der Veranstaltung bekannt gegebene Werke. | |
| regelmäßig | |
| Deutsch | |
| Geeignet für Lehramtsstudierende, Nebenfachstudierende. | |
| Moore-Automat, Endliche Automaten, Mealy-Automat, Determinismus, Nicht-Determinismus, Typ-3-Grammatik | |